A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning

摘要

Although the use of metric fluents is fundamental to many practical planningproblems, the study of heuristics to support fully automated planners workingwith these fluents remains relatively unexplored. The most widely usedheuristic is the relaxation of metric fluents into interval-valued variables--- an idea first proposed a decade ago. Other heuristics depend on domainencodings that supply additional information about fluents, such as capacityconstraints or other resource-related annotations. A particular challenge tothese approaches is in handling interactions between metric fluents thatrepresent exchange, such as the transformation of quantities of raw materialsinto quantities of processed goods, or trading of money for materials. Theusual relaxation of metric fluents is often very poor in these situations,since it does not recognise that resources, once spent, are no longer availableto be spent again. We present a heuristic for numeric planning problemsbuilding on the propositional relaxed planning graph, but using a mathematicalprogram for numeric reasoning. We define a class of producer--consumer planningproblems and demonstrate how the numeric constraints in these can be modelledin a mixed integer program (MIP). This MIP is then combined with a metricRelaxed Planning Graph (RPG) heuristic to produce an integrated hybridheuristic. The MIP tracks resource use more accurately than the usualrelaxation, but relaxes the ordering of actions, while the RPG captures thecausal propositional aspects of the problem. We discuss how these twocomponents interact to produce a single unified heuristic and go on to explorehow further numeric features of planning problems can be integrated into theMIP. We show that encoding a limited subset of the propositional problem toaugment the MIP can yield more accurate guidance, partly by exploitingstructure such as propositional landmarks and propositional resources. Ourresults show that the use of this heuristic enhances scalability on problemswhere numeric resource interaction is key in finding a solution.